﻿#define _CRT_SECURE_NO_WARNINGS 1

//#include<stdio.h>
//#include<stdlib.h>
//#include<time.h>
//#include<string.h>
//void PrintArray(int* a, int n)
//{
//	for (int i = 0; i < n; ++i)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//}
//void Swap(int* p1, int* p2)
//{
//	int tmp = *p1;
//	*p1 = *p2;
//	*p2 = tmp;
//}
//// hoare
//// [left, right]
//int PartSort1(int* a, int left, int right)
//{
//	int keyi = left;
//	while (left < right)
//	{
//		// 右边找⼩
//		while (left < right && a[right] >= a[keyi])
//		{
//			--right;
//		}
//		// 左边找⼤
//		while (left < right && a[left] <= a[keyi])
//		{
//			++left;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[keyi], &a[left]);
//	return left;
//}
//// 前后指针
//int PartSort2(int* a, int left, int right)
//{
//	int prev = left;
//	int cur = left + 1;
//	int keyi = left;
//	while (cur <= right)
//	{
//		if (a[cur] < a[keyi] && ++prev != cur)
//		{
//			Swap(&a[prev], &a[cur]);
//		}
//		++cur;
//	}
//	Swap(&a[prev], &a[keyi]);
//	keyi = prev;
//	return keyi;
//}
//typedef struct
//{
//	int leftKeyi;
//	int rightKeyi;
//}KeyWayIndex;
////// 三路划分
////KeyWayIndex PartSort3Way(int* a, int left, int right)
////{
////	int key = a[left];
////	// left和right指向就是跟key相等的区间
////	// [开始, left-1][left, right][right+1, 结束]
////	int cur = left + 1;
////	while (cur <= right)
////	{
////		// 1、cur遇到⽐key⼩，⼩的换到左边，同时把key换到中间位置
////		// 2、cur遇到⽐key⼤，⼤的换到右边
////		if (a[cur] < key)
////		{
////			Swap(&a[cur], &a[left]);
////			++cur;
////			++left;
////		}
////		else if (a[cur] > key)
////		{
////			Swap(&a[cur], &a[right]);
////			--right;
////		}
////		else
////		{
////			++cur;
////		}
////	}
////	KeyWayIndex kwi;
////	kwi.leftKeyi = left;
////	kwi.rightKeyi = right;
////	return kwi;
////}
//void TestPartSort1()
//{
//	int a1[] = { 6,1,7,6,6,6,4,9 };
//	int a2[] = { 3,2,3,3,3,3,2,3 };
//	int a3[] = { 2,2,2,2,2,2,2,2 };
//	PrintArray(a1, sizeof(a1) / sizeof(int));
//	int keyi1 = PartSort1(a1, 0, sizeof(a1) / sizeof(int) - 1);
//	PrintArray(a1, sizeof(a1) / sizeof(int));
//	printf("hoare keyi:%d\n\n", keyi1);
//	PrintArray(a2, sizeof(a2) / sizeof(int));
//	int keyi2 = PartSort1(a2, 0, sizeof(a2) / sizeof(int) - 1);
//	PrintArray(a2, sizeof(a2) / sizeof(int));
//	printf("hoare keyi:%d\n\n", keyi2);
//	PrintArray(a3, sizeof(a3) / sizeof(int));
//	int keyi3 = PartSort1(a3, 0, sizeof(a3) / sizeof(int) - 1);
//	PrintArray(a3, sizeof(a3) / sizeof(int));
//	printf("hoare keyi:%d\n\n", keyi3);
//}
//void TestPartSort2()
//{
//	int a1[] = { 6,1,7,6,6,6,4,9 };
//	int a2[] = { 3,2,3,3,3,3,2,3 };
//	int a3[] = { 2,2,2,2,2,2,2,2 };
//	PrintArray(a1, sizeof(a1) / sizeof(int));
//	int keyi1 = PartSort2(a1, 0, sizeof(a1) / sizeof(int) - 1);
//	PrintArray(a1, sizeof(a1) / sizeof(int));
//	printf("前后指针 keyi:%d\n\n", keyi1);
//	PrintArray(a2, sizeof(a2) / sizeof(int));
//	int keyi2 = PartSort2(a2, 0, sizeof(a2) / sizeof(int) - 1);
//	PrintArray(a2, sizeof(a2) / sizeof(int));
//	printf("前后指针 keyi:%d\n\n", keyi2);
//	PrintArray(a3, sizeof(a3) / sizeof(int));
//	int keyi3 = PartSort2(a3, 0, sizeof(a3) / sizeof(int) - 1);
//	PrintArray(a3, sizeof(a3) / sizeof(int));
//	printf("前后指针 keyi:%d\n\n", keyi3);
//}
////void TestPartSort3()
////{
////	//int a0[] = { 6,1,2,7,9,3,4,5,10,4 };
////	int a1[] = { 6,1,7,6,6,6,4,9 };
////	int a2[] = { 3,2,3,3,3,3,2,3 };
////	int a3[] = { 2,2,2,2,2,2,2,2 };
////	PrintArray(a1, sizeof(a1) / sizeof(int));
////	KeyWayIndex kwi1 = PartSort3Way(a1, 0, sizeof(a1) / sizeof(int) - 1);
////	PrintArray(a1, sizeof(a1) / sizeof(int));
////	printf("3Way keyi:%d,%d\n\n", kwi1.leftKeyi, kwi1.rightKeyi);
////	PrintArray(a2, sizeof(a2) / sizeof(int));
////	KeyWayIndex kwi2 = PartSort3Way(a2, 0, sizeof(a2) / sizeof(int) - 1);
////	PrintArray(a2, sizeof(a2) / sizeof(int));
////	printf("3Way keyi:%d,%d\n\n", kwi2.leftKeyi, kwi2.rightKeyi);
////	PrintArray(a3, sizeof(a3) / sizeof(int));
////	KeyWayIndex kwi3 = PartSort3Way(a3, 0, sizeof(a3) / sizeof(int) - 1);
////	PrintArray(a3, sizeof(a3) / sizeof(int));
////	printf("3Way keyi:%d,%d\n\n", kwi3.leftKeyi, kwi3.rightKeyi);
////}
//int GetKey(int* arr, int left, int right)
//{
//	int i = rand();
//	return arr[left + i % (right - left + 1)];
//}
//
//
//// 三路划分，通过引用参数返回左右边界索引
//void PartSort3Way(int* a, int left, int right, int* leftKeyi, int* rightKeyi) {
//	int key = GetKey(a, left, right);
//	int cur = left + 1;
//	while (cur <= right) 
//	{
//		if (a[cur] < key) 
//		{
//			Swap(&a[cur], &a[left]);
//			++cur;
//			++left;
//		}
//		else if (a[cur] > key) Swap(&a[cur], &a[--right]);
//		else ++cur;
//	}
//	*leftKeyi = left;
//	*rightKeyi = right;
//}
//
//void TestPartSort3() {
//	int a1[] = { 6, 1, 7, 6, 6, 6, 4, 9 };
//	int a2[] = { 3, 2, 3, 3, 3, 3, 2, 3 };
//	int a3[] = { 2, 2, 2, 2, 2, 2, 2, 2 };
//	int leftKeyi1, rightKeyi1;
//	PrintArray(a1, sizeof(a1) / sizeof(int));
//	PartSort3Way(a1, 0, sizeof(a1) / sizeof(int) - 1, &leftKeyi1, &rightKeyi1);
//	PrintArray(a1, sizeof(a1) / sizeof(int));
//	printf("三路划分:%d,%d\n\n", leftKeyi1, rightKeyi1);
//
//	int leftKeyi2, rightKeyi2;
//	PrintArray(a2, sizeof(a2) / sizeof(int));
//	PartSort3Way(a2, 0, sizeof(a2) / sizeof(int) - 1, &leftKeyi2, &rightKeyi2);
//	PrintArray(a2, sizeof(a2) / sizeof(int));
//	printf("三路划分:%d,%d\n\n", leftKeyi2, rightKeyi2);
//
//	int leftKeyi3, rightKeyi3;
//	PrintArray(a3, sizeof(a3) / sizeof(int));
//	PartSort3Way(a3, 0, sizeof(a3) / sizeof(int) - 1, &leftKeyi3, &rightKeyi3);
//	PrintArray(a3, sizeof(a3) / sizeof(int));
//	printf("三路划分:%d,%d\n\n", leftKeyi3, rightKeyi3);
//}
//
//int main()
//{
//	//TestPartSort1();
//	//TestPartSort2();
//	TestPartSort3(); // 三路划分比较对于重复数据的处理更加高效
//	return 0;
//}